package com.ztom.daily.n2022.m6;

import java.util.Arrays;

/**
 * 高度检查器
 * <p>
 * https://leetcode.cn/problems/height-checker/
 *
 * @author ZhangTao
 */
public class Day13HeightChecker {

    public int heightChecker1(int[] heights) {
        int n = heights.length;
        int[] expected = new int[n];
        System.arraycopy(heights, 0, expected, 0, n);

        Arrays.sort(expected);
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (heights[i] != expected[i]) {
                res++;
            }
        }
        return res;
    }

    public int heightChecker(int[] heights) {
        int max = 0;
        for (int height : heights) {
            max = Math.max(max, height);
        }

        int[] buckets = new int[max + 1];
        for (int height : heights) {
            buckets[height]++;
        }

        int index = 0;
        int res = 0;
        for (int i = 1; i <= max; i++) {
            for (int j = 1; j <= buckets[i]; j++) {
                if (heights[index] != i) {
                    res++;
                }
                index++;
            }
        }
        return res;
    }
}
